package _47

// 使用图算法, dfs/bfs 顶点个数-连通分量个数
func removeStones(stones [][]int) int {
	// 访问的顶点记录
	visited := make(map[int]bool)
	// 连通分量的个数
	cnt := 0

	q := make([]int, 0)
	for i := 0; i < len(stones); i++ {
		if visited[i] == false {
			cnt += 1
			q = append(q, i)
		}

		for len(q) > 0 {
			curStone := q[0]
			q = q[1:]
			visited[curStone] = true
			neighbors := findNeighbors(curStone, stones)
			for _, neighbor := range neighbors {
				if !visited[neighbor] {
					q = append(q, neighbor)
				}
			}
		}

	}

	return len(stones) - cnt
}

func findNeighbors(curIdx int, stones [][]int) []int {
	neighbors := make([]int, 0)
	stone := stones[curIdx]
	for i := 0; i < len(stones); i++ {
		tmpStone := stones[i]
		if i == curIdx {
			continue
		}
		if stone[0] == tmpStone[0] || stone[1] == tmpStone[1] {
			neighbors = append(neighbors, i)
		}
	}
	return neighbors
}
